package listbyorder.access001_100.test76;

import java.util.HashMap;

/**
 * 最小覆盖子串
 * 滑动窗口经典题，适合二刷
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 9:14
 */
public class Solution1 {

    public String minWindow(String s, String t) {
        // 首先将待识别的t放入HashMap中进行构造
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 定义滑动窗口的指针
        int left = 0;
        int right = 0;
        int ans_left = 0;
        int ans_right = -1;
        int ans_len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                // 去除之后，判断当前的map集合是否全部被利用到了
                while (match(map)) {
                    int cur_len = right - left + 1;
                    if (cur_len < ans_len) {
                        ans_len = cur_len;
                        ans_left = left;
                        ans_right = right;
                    }
                    char key = s.charAt(left);
                    if (map.containsKey(key)) {
                        map.put(key, map.get(key) + 1);
                    }
                    // left指针右移
                    left++;
                }
            }
            right++;
        }
        return s.substring(ans_left, ans_right + 1);
    }

    private boolean match(HashMap<Character, Integer> map) {
        for (Character c : map.keySet()) {
            if (map.get(c) > 0) {
                return false;
            }
        }
        return true;
    }
}
